// kotori和气球(排列)
#include <iostream>
using namespace std;

const int mod = 109;
int n, m, res;

int main()
{
    cin >> n >> m;
    res = n;
    for (int i = 1; i < m; i++)
    {
        res = res * (n - 1) % mod;
    }
    cout << res << endl;
    return 0;
}

// 走迷宫(BFS最短路)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
bool used[1001][1001];
using pii = pair<int, int>;
queue<pii> q;
int n, m, step, flag;
int xs, ys, xt, yt;

int main()
{
    cin >> n >> m;
    cin >> xs >> ys >> xt >> yt;
    vector<string> vs(n + 1);
    for (int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;
        vs[i] = " " + s;
    }
    if (vs[xt][yt] == '.') 
    {
        q.push({xs, ys});
        used[xs][ys] = true;
        while (q.size())
        {
            step++;
            int sz = q.size();
            while (sz--)
            {
                auto [a, b] = q.front();
                q.pop();
                for (int i = 0; i < 4; i++)
                {
                    int x = a + dx[i], y = b + dy[i];
                    if (x == xt && y == yt)
                    {
                        flag = 1;
                        break;
                    }
                    if (x > 0 && x <= n && y > 0 && y <= m && !used[x][y] && vs[x][y] == '.')
                    {
                        used[x][y] = true;
                        q.push({x, y});
                    }
                }
                if (flag) break;
            }
            if (flag) break;
        }
    }
    cout << (step > 0 ? step : -1) << endl;
    return 0;
}

// 主持人调度（二）(贪心+优先级队列)
class Solution {
    public:
        int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
            priority_queue<int, vector<int>, greater<int>> pq;
            sort(startEnd.begin(), startEnd.end());
            pq.push(startEnd[0][1]);
            for (int i = 1; i < n; i++)
            {
                if (startEnd[i][0] >= pq.top()) pq.pop();
                pq.push(startEnd[i][1]);
            }
            return pq.size();
        }
    };
    